1. Field of the Invention
The present invention relates to binary digital multipliers.
2. Description of the Prior Art
The principle of binary digit multiplication is well known: the multiplicand is multiplied by the lowest weight digit of the multiplier, then by the digit with the immediately higher weight and so on up to the highest weight; the result each time is a partial product, and the different partial products are added with a lateral leftward shift by a digit between each partial product and the preceding one. The sum of all the partial products progressively shifted forms the result of the multiplication.
Concretely, a partial product can be stored in a register, the result shifted by a rank, added to the next partial product, the result stored in the same register and so on. This is a sequential procedure which is long.
So efforts have been made to design multipliers in which all the partial products are generated simultaneously and added (combinatory and not sequential logic), and, for these multipliers, attempts have been made to increase the working speed, either by reducing the time for adding the partial products or by reducing the number of these partial products.
The adding time may be reduced by using improved adders such as:
adders with carry-over safeguard in which the carry-overs of the elementary additions of the digits of a number are not propagated from one digit to the next but are kept to be added as a whole; PA1 adders with anticipated carry-over, in which the value of the carry-over is forecast as a function of the inputs instead of waiting for propagation thereof; PA1 adders connected together in a particular pattern such as the Wallace tree for grouping together the partial products progressively three by three.
Independently of the reduction of adding time, the number of partial products to be added may also be reduced by appropriately coding the bits of the multiplier. With Booth's algorithm and the variations thereof, only (n+1)/2 partial products are generated instead of n for a multiplier with n digits, each of these partial products having four or five possible values which are, X, -X, 2X and possibly -2X, X being the multiplicand. But this kind of manipulation increases the complexity of the circuit, so the space required thereby.